Home | | Latest | About | Random
# 38 Application to discrete dynamical systems - Stochastic matrices and equilibrium vectors.
Let us apply some of this new found "eigen-knowledge" to solve some interesting problem. We will look at discrete dynamical systems.
Roughly speaking, a discrete dynamical starts with a list of state values, and after each iteration, each of the value changes according to some specified rules. What we like to know is (1) how to model it, if reasonable, and (2) find equilibrium state solutions.
We will use a very concrete example to illustrate this.
## Migration of citizens among cities.
Suppose in a nation there are three cities $A,B,C$.
Suppose it is observed that every year the following things happen:
- $\frac{1}{3}$ of people in $A$ stay in $A$ ; $\frac{1}{6}$ of people in $A$ move to $B$ ; $\frac{1}{2}$ of people in $A$ move to $C$.
- $\frac{1}{4}$ of people in $B$ move to $A$; $\frac{1}{2}$ of people in $B$ stay in $B$ ; $\frac{1}{4}$ of people in $B$ move to $C$.
- $\frac{3}{5}$ of people in $C$ move to $A$ ; $\frac{1}{5}$ of people in $C$ move to $B$ ; $\frac{1}{5}$ of people in $C$ stay in $C$.
Suppose this happens every year, and no one dies and no newborns. What we like to know is:
- How do we model this with linear algebra?
- Is there an equilibrium solution, a distribution of population that after each year the population is not changing any more.
- And, at equilibrium, which city is the most popular one? Which is least?
- If the nation has 1 million total people, to the nearest integer, how many citizens are in each city at equilibrium?
## An arrow-and-dot graph representation of the problem.
Let us represent the problem with a **graph**. A mathematical graph is a collection of dots and arrows.
It would look like this for our situation:
![[1 teaching/smc-spring-2024-math-13/linear-algebra-notes/---files/stochastic.svg]]
(This is the graph-theoretical graph, not the graph an algebra students plots on a graph paper.)
This is kind of nice as a visualization of what is happening each year, how the populations are migrating to each other cities. However, it is not quite clear what would happen in the long run or at equilibrium.
## A stochastic matrix to model the problem.
Let us denote $\vec p_{0} = \begin{pmatrix}a\\b\\c\end{pmatrix}$ to be the initial population of each of the cities, where $A$ has $a$ many citizens, $B$ has $b$ many, and $C$ has $c$ many.
Then, after one iteration (one year in this case) of the system, we have the population of each city after one iteration as follows: $$
\begin{align*}
\text{new pop. of }A = \frac{1}{3}a + \frac{1}{4}b + \frac{3}{5}c \\
\text{new pop. of }B = \frac{1}{6}a + \frac{1}{2}b + \frac{1}{5}c \\
\text{new pop. of }C = \frac{1}{2}a + \frac{1}{4}b + \frac{1}{5}c
\end{align*}
$$
Hold on, this is _a linear system of equations!_ If we denote $\vec p_{1}$ as the new population after 1 iteration, then we have the matrix-vector equation $$
\vec p_{1} = \underbrace{\begin{pmatrix} \frac{1}{3} & \frac{1}{4} & \frac{3}{5} \\
\frac{1}{6} & \frac{1}{2} & \frac{1}{5} \\
\frac{1}{2} & \frac{1}{4} & \frac{1}{5}\end{pmatrix}}_{M} \vec p_{0}.
$$
Let us denote the matrix as $M$. Notice that each column sums to 1, this is called a **stochastic matrix**.
Using the same idea, if we denote $\vec p_{2}$ as the new population after 1 iteration from $\vec p_{1}$, then we have $$
\vec p_{2} = M \vec p_{1} = M^{2}\vec p_0.
$$
And in general, after $k$ iterations, we have the **stochastic model** $$
\vec p_{k} = M^{k} \vec p_{0}
$$where $$
M = \begin{pmatrix} \frac{1}{3} & \frac{1}{4} & \frac{3}{5} \\
\frac{1}{6} & \frac{1}{2} & \frac{1}{5} \\
\frac{1}{2} & \frac{1}{4} & \frac{1}{5}\end{pmatrix}
$$is the **stochastic matrix of this discrete dynamical system.**
This is how we can model the problem with linear algebra. If we so wish, we could compute the powers of $M$. We will not do that here for now.
## Equilibrium solution vector. (Steady-state solution.)
An **equilibrium solution vector** to a stochastic model problem is a vector $\vec p_{\text{eq}}$ such that after each iteration by the system, it remains unchanged. So it is a vector $\vec p_{\text{eq}}$ such that $$
M\vec p_{\text{eq}} = \vec p_{\text{eq}}.
$$You, being the astute student, see that $\vec p_{\text{eq}}$ is just an eigenvector to $M$ of eigenvalue $1$! Before we start, you could say, well, wouldn't $\vec p_{\text{eq}} = \vec 0$ work? Yes, but that is a trivial equilibrium solution. Let us look instead for a nontrivial solution.
So to find equilibrium solution vectors we simply need to look at the eigenspace of $1$, namely $E_{1} = \ker(M-I)$.
Let us compute for our case, note
$$
\begin{align*}
E_{1} & = \ker (M-I) = \ker \begin{pmatrix} \frac{-2}{3} & \frac{1}{4} & \frac{3}{5} \\
\frac{1}{6} & \frac{-1}{2} & \frac{1}{5} \\
\frac{1}{2} & \frac{1}{4} & \frac{-4}{5}\end{pmatrix} \\
& = \ker \begin{pmatrix} -40 & 15 & 36 \\
10 & -30 & 12 \\
30 & 15 & -48 \end{pmatrix} \\
&= \ker \begin{pmatrix}
10 & -30 & 12 \\
0 & -105 & 84\\
0 & 105 & 84 \end{pmatrix} \\
&= \ker \begin{pmatrix}
5 & -15 & 6 \\
0 & 5 & -4\\
0 & 0 & 0 \end{pmatrix} \\
&= \ker \begin{pmatrix}
5 & 0 & -6 \\
0 & 5 & -4\\
0 & 0 & 0 \end{pmatrix} \\
&=\operatorname{span}\{ \begin{pmatrix} \frac{6}{5}\\ \frac{4}{5} \\1\end{pmatrix}\}
\end{align*}
$$So $\begin{pmatrix} \frac{6}{5}\\ \frac{4}{5} \\ 1\end{pmatrix}$is an equilibrium solution vector! In fact, any scalar multiple of $\begin{pmatrix} \frac{6}{5}\\ \frac{4}{5} \\ 1\end{pmatrix}$ is an equilibrium solution vector, as $E_{1} = \operatorname{span}\begin{pmatrix} \frac{6}{5}\\ \frac{4}{5} \\1\end{pmatrix}\}$. We can re-scale it so that it has most reduced integer ratios, so $E_{1} = \operatorname{span} \{\begin{pmatrix}6\\4\\5\end{pmatrix}\}$.
This means that at equilibrium, the cities would have populations $$
A_{\text{eq}}:B_{\text{eq}}:C_{\text{eq}} = 6:4:5.
$$(Technically $0:0:0$ is also an equilibrium, but that is the trivial equilibrium point.)
This reveals that at equilibrium, city $A$ is most popular, followed by $C$, then lastly $B$.
And, if there is 1 million = $10^{6}$ total population, then at equilibrium we would have $$
\begin{align*}
A_{\text{eq}} = 10^{6} \cdot \frac{6}{15}= 400000 \\
B_{\text{eq}} = 10^{6} \cdot \frac{4}{15} \approx 266667 \\
C_{\text{eq}} = 10^{6} \cdot \frac{5}{15} \approx 333333
\end{align*}
$$where $A_{\text{eq}},B_{\text{eq}},C_{\text{eq}}$ are the equilibrium populations of cities $A,B,C$, rounded to the nearest integer. (Note this normalization calculation cannot be done if we have trivial ratios $0:0:0$, if we start with a total of 1 million people! Think about it.)
Isn't this neat!
**Remark.** Besides analyzing population migration patterns, this type of "stochastic analysis" is ubiquitous in many similar problems, like figuring out which aisle a customer would likely to stay at in a super market, or which webpage a visitor would likely to stay on or move to -- this is how roughly Google's PageRank algorithm work!
## Postscript and loose ends.
Well, above analysis is great, but we sort of just assumed that the equilibrium solution vector $\vec p_\text{eq}$ would just exist for our stochastic matrix $M$. Is this always true? Well, almost.
Let us make some definitions for us.
A square matrix $M$ is **stochastic** if every entry in $M$ is non-negative, and that each column sums to 1. (Sometimes this is further called a _left stochastic matrix_.)
Now, if $M$ is a stochastic matrix such that there exists some positive integer power $k$ where $M^{k}$ is a matrix where every entry is _strictly positive_, then $M$ is called an **irreducible stochastic matrix**.
Then we have the celebrated result,
> **Perron-Frobenius.**
> If $M$ is an irreducible stochastic matrix, then $M$ has an eigenvalue $1$ with algebraic multiplicity of $1$. In particular, there exists a nontrivial equilibrium solution vector $\vec p_{eq}$ such that $M\vec p_{\text{eq}} = \vec p_{\text{eq}}$.
For our example above of 3 cities, the matrix $M$ is already all positive entries, so $M$ itself is irreducible. Whence by Perron-Frobenius, a nontrivial equilibrium solution exist.
If the matrix $M$ is not irreducible, then it is not clear what would happen.
In any case, this is perhaps one of the most important theorem in the 20th century, in terms of usefulness. The study of the discrete dynamical system is part of a larger story called **Markov process**, if you are interested I hope one day you learn more about it!